1 // Convex Hull: Andrew's Monotone Chain Convex Hull
2 // Complexity: O(n log n) (But lower constant than Graham Scan)
4 typedef long long CoordType
;
8 bool operator <(const Point
&p
) const {
9 return x
< p
.x
|| (x
== p
.x
&& y
< p
.y
);
13 // 2D cross product. Returns a positive value, if OAB makes a
14 // counter-clockwise turn, negative for clockwise turn, and zero
15 // if the points are collinear.
16 CoordType
cross(const Point
&O
, const Point
&A
, const Point
&B
){
17 return (A
.x
- O
.x
) * (B
.y
- O
.y
) - (A
.y
- O
.y
) * (B
.x
- O
.x
);
20 // Returns a list of points on the convex hull in
21 // counter-clockwise order. Note: the last point in the returned
22 // list is the same as the first one.
23 vector
<Point
> convexHull(vector
<Point
> P
){
24 int n
= P
.size(), k
= 0;
26 // Sort points lexicographically
27 sort(P
.begin(), P
.end());
29 for (int i
= 0; i
< n
; i
++) {
30 while (k
>= 2 && cross(H
[k
-2], H
[k
-1], P
[i
]) <= 0) k
--;
34 for (int i
= n
-2, t
= k
+1; i
>= 0; i
--) {
35 while (k
>= t
&& cross(H
[k
-2], H
[k
-1], P
[i
]) <= 0) k
--;